package graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 基于邻接表的无向图
 */
public class TGraph {
    /**
     * 顶点数
     */
    private final int V;

    /**
     * 边数
     */
    private int E;

    /**
     * 邻接表的点
     */
    class Node {
        int v;
        Node next;

        public Node(int v, Node next) {
            this.v = v;
            this.next = next;
        }

        public Node() {
        }

    }

    /**
     * 邻接表
     */
    private Node[] adjacencyTable;

    /**
     * 构造函数
     * 
     * @param v 顶点数
     */
    public TGraph(int v) {
        this.V = v;
        this.adjacencyTable = new Node[v];
        for (int i = 0; i < v; i++) {
            this.adjacencyTable[i] = new Node(i + 1, null);
        }
    }

    /**
     * 验证输出顶点的正确性
     * 
     * @param v
     * @return
     */
    public boolean validateV(int v) {
        if (v < 1 || v > V) {
            System.out.println("请输入在1到" + V + "之间的顶点");
            return false;
        } else {
            return true;
        }
    }

    /**
     * 添加边，联通v和w
     * 
     * @param v
     * @param w
     */
    public void addEdge(int v, int w) {
        if (validateV(v) && validateV(w)) {
            Node tmp = this.adjacencyTable[v - 1].next;
            this.adjacencyTable[v - 1].next = new Node(w, null);
            this.adjacencyTable[v - 1].next.next = tmp;

            tmp = this.adjacencyTable[w - 1].next;
            this.adjacencyTable[w - 1].next = new Node(v, null);
            this.adjacencyTable[w - 1].next.next = tmp;
            E++;
        }
    }

    /**
     * 获取顶点数
     */
    public int V() {
        return V;
    }

    /**
     * 获取边数
     * 
     * @return
     */
    public int E() {
        return E;
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < this.adjacencyTable.length; i++) {
            buffer.append(this.adjacencyTable[i].v + ":");
            Node tmp = this.adjacencyTable[i].next;
            while (tmp != null) {
                buffer.append(" " + tmp.v);
                tmp = tmp.next;
            }
            buffer.append("\n");
        }
        return buffer.toString();
    }

    /**
     * 获取v的所有邻接节点
     * 
     * @param v
     * @return
     */
    public int[] adj(int v) {
        if (validateV(v)) {
            int[] tmp = new int[V];
            int count = 0;
            Node hNode = adjacencyTable[v - 1].next;
            while (hNode != null) {
                tmp[count] = hNode.v;
                count++;
                hNode = hNode.next;
            }
            int[] returnValue = new int[count];
            for (int i = 0; i < count; i++) {
                returnValue[i] = tmp[i];
            }
            return returnValue;
        } else {
            return null;
        }
    }

    /**
     * 获取节点v的度
     * 
     * @param v
     * @return
     */
    public int getDegree(int v) {
        if (validateV(v)) {
            return adj(v).length;
        } else {
            return 0;
        }
    }

    /**
     * 深度优先搜索
     * 
     * @param v 深度优先搜索开始的点
     * @return
     */
    public void DFS(int v) {
        boolean[] visited = new boolean[this.V];
        DFSHelper(visited, v);
    }

    /**
     * 深度优先搜索的辅助实现函数
     * 
     * @param visited 存储着是否被遍历的数据
     * @param v       当前遍历节点
     */
    public void DFSHelper(boolean[] visited, int v) {
        if (visited[v - 1] == false) {
            visited[v - 1] = true;
            System.out.println(v);
            for (int i : this.adj(v)) {
                DFSHelper(visited, i);
            }
        }
    }

    /**
     * 广度优先搜索
     * 
     * @param v 从v点开始的广度优先搜索
     */
    public void BFS(int v) {
        boolean[] visited = new boolean[this.V];
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(v);

        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            if (visited[tmp - 1] == false) {
                visited[tmp - 1] = true;
                System.out.println(tmp);
                for (int i : this.adj(tmp)) {
                    queue.add(i);
                }
            }
        }
    }


    /**
     * 单源最短路径算法
     * @param v 出发点
     */
    public int[] singleSourceShortestPath(int v){
        /**
         * dists记录v到每个节点的距离, -1表示不联通
         */
        int[] dists = new int[this.V];
        for (int i = 0; i < this.V; i++){
            dists[i] = -1;
        }
        // 和自己的距离为0
        dists[v - 1] = 0;
        
        // 存储路径
        int[] paths = new int[this.V];
        paths[v - 1] = v;
        
        // 广度优先遍历
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);

        while (!queue.isEmpty()){
            int tmp = queue.poll();
            for (Integer i : this.adj(tmp)) {
                if (dists[i - 1] == -1){
                    dists[i - 1] = dists[tmp - 1] + 1;
                    paths[i - 1] = tmp;
                    queue.add(i);
                }
            }
        }

        return dists;
    }
}
